package Sequence;

public class Test0494 {
    public static void main(String[] args) {
        new Solution0494_1().findTargetSumWays(new int[]{1,1,1,1,1},3);
    }
}

class Solution0494_1 {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) sum+=num;
        if (target<-sum||target>sum) return 0;

        int[] record = new int[sum * 2 + 1];
        record[sum+nums[0]]+=1;
        record[sum-nums[0]]+=1;

        for (int i = 1; i < nums.length; i++) {
            int num = nums[i];

            int[] temp = new int[sum * 2 + 1];
            for (int j = 0; j < record.length; j++) {
                int re = record[j];
                if (re!=0){
                    temp[j-num]+=re;
                    temp[j+num]+=re;
                }
            }
            record = temp;
        }


        return record[sum+target];
    }
}